#include <bits/stdc++.h>
using namespace std;

/*

*/

// 法一
const int maxn = 100000 + 100;  // 最大节点数，预留足够空间

class TrieTree {
public:
    struct TrieNode {
        int son[2];  // 二进制位分支，0/1两个子节点[3](@ref)
        void clear() {
            son[0] = son[1] = 0;  // 初始化子节点为空
        }
    } t[maxn * 32];  // 预分配静态数组空间（每个数最多31层）
    int root, size;   // 根节点指针和节点计数器

    // 初始化Trie树
    void clear() {
        root = size = 1;  // 根节点从1开始计数
        t[root].clear();
    }

    // 插入数字的二进制表示（从高位到低位）
    void insert(int num) {
        int p = root;
        for (int i = 30; i >= 0; --i) {  // 处理31位二进制数
            int x = (num >> i) & 1;      // 提取当前二进制位
            if (t[p].son[x] == 0) {      // 新建路径节点
                ++size;
                t[size].clear();
                t[p].son[x] = size;
            }
            p = t[p].son[x];  // 移动到子节点
        }
    }

    // 查询与num异或最大的值
    int query(int num) {
        int p = root, ans = 0;
        if (t[p].son[0] == 0 && t[p].son[1] == 0) {
            return -1;  // 空树时返回-1
        }
        for (int i = 30; i >= 0; --i) {
            int x = (num >> i) & 1;
            // 优先选择相反位（最大化异或结果）
            if (t[p].son[x ^ 1] > 0) {  // 存在相反路径
                ans |= 1 << i;         // 累加该位的贡献值
                p = t[p].son[x ^ 1];   // 走相反路径
            } else {                   // 只能走相同路径
                p = t[p].son[x];
            }
        }
        return ans;
    }
} T;
class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        T.clear();  // 初始化Trie树
        sort(nums.begin(), nums.end());  // 排序便于逐步插入
        
        // 处理查询：按mi升序排序，保留原始索引
        vector<pair<int, int>> q;
        for (int i = 0; i < queries.size(); ++i) {
            q.emplace_back(queries[i][1], i);  // (mi, 原始索引)
        }
        sort(q.begin(), q.end());

        vector<int> ans(queries.size());
        int j = 0;  // nums插入指针
        
        // 按mi升序处理每个查询
        for (auto& [mi, idx] : q) {
            // 插入所有<=当前mi的数字
            while (j < nums.size() && nums[j] <= mi) {
                T.insert(nums[j++]);
            }
            // 获取该查询结果（自动处理空树返回-1的情况）
            ans[idx] = T.query(queries[idx][0]);
        }
        return ans;
    }
};

// 法二
class Solution {
    vector<array<int, 2>> son; // 动态存储Trie节点[9](@ref)
    int idx = 0;
    
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        son.reserve(200000);    // 预分配合理空间[3](@ref)
        son.push_back({0,0});   // 初始化根节点[9](@ref)
        
        sort(nums.begin(), nums.end());
        
        // 处理查询并排序[1](@ref)
        vector<tuple<int, int, int>> sorted_queries;
        for(int i = 0; i < queries.size(); ++i) {
            sorted_queries.emplace_back(queries[i][1], queries[i][0], i);
        }
        sort(sorted_queries.begin(), sorted_queries.end());
        
        vector<int> res(queries.size(), -1);
        int j = 0;
        
        for(auto& q : sorted_queries) {
            auto [mi, xi, index] = q;
            
            // 插入满足条件的元素[3](@ref)
            while(j < nums.size() && nums[j] <= mi) {
                insert(nums[j++]);
            }
            
            res[index] = (j == 0) ? -1 : query(xi);
        }
        return res;
    }

private:
    void insert(int x) {
        int p = 0;
        for(int i = 30; i >= 0; --i) {
            int u = (x >> i) & 1;
            if(!son[p][u]) {
                son.push_back({0,0}); // 动态扩展节点[9](@ref)
                son[p][u] = son.size()-1;
            }
            p = son[p][u];
        }
    }
    
    int query(int x) {
        int p = 0, res = 0;
        for(int i = 30; i >= 0; --i) {
            int u = (x >> i) & 1;
            int desired = u ^ 1; // 优先选择相反位[3](@ref)
            
            if(son[p][desired]) {
                res |= 1 << i;
                p = son[p][desired];
            } else {
                p = son[p][u];
            }
        }
        return res;
    }
};

// 法三
// Trie树节点结构，每个节点存储0/1两个分支和经过该节点的数字数量
struct Node {
    int son[2],
        cnt; // son[0]左分支(0)，son[1]右分支(1)，cnt经过该节点的数字数量
    void init() { son[0] = son[1] = cnt = 0; }
} node[4000000];

// 支持动态插入删除的二进制Trie树
struct Trie {
    int tot = 0; // 节点总数
    int H = 0;   // 处理的最高二进制位数（由最大值决定）
    int siz = 0; // 当前树中存储的数字数量

    // 初始化Trie，maxv决定处理的二进制位数（如maxv=INT_MAX则处理31位）
    void init(int maxv) {
        H = std::__lg(maxv) + 1; // 计算需要的二进制位数
        tot = siz = 0;
        node[0].init(); // 初始化根节点
    }

    // 创建新节点（预分配内存模式）
    int newnode() {
        tot += 1;
        node[tot].init();
        return tot;
    }

    // 插入数字u到Trie中，按二进制位构建路径
    void insert(int u) {
        int p = 0;
        for (int i = H; i >= 0; i--) { // 从最高位到最低位处理
            int d = (u >> i) & 1;      // 获取当前位的值
            if (node[p].son[d] == 0) { // 路径不存在则创建新节点
                node[p].son[d] = newnode();
            }
            p = node[p].son[d];
            node[p].cnt += 1; // 更新路径上的节点计数
        }
        siz += 1; // 维护当前树中元素数量
    }

    // 从Trie中移除数字u（需要保证u存在）
    void remove(int u) {
        int p = 0;
        for (int i = H; i >= 0; i--) {
            int d = (u >> i) & 1;
            p = node[p].son[d];
            node[p].cnt -= 1; // 减少路径上的节点计数
        }
        siz -= 1; // 维护当前树中元素数量
    }

    // 查找与u异或结果最大的数字，返回异或结果值
    int find(int u) {
        int p = 0, ans = 0;
        for (int i = H; i >= 0; i--) {
            int d = (u >> i) & 1;
            int x = node[p].son[d ^ 1]; // 优先选择相反位以获得最大异或

            // 若相反位路径存在且未被删除，则走该路径
            if (node[x].cnt) {
                p = x;
                ans |= (d ^ 1) << i; // 累计当前位的值到结果
            } else {                 // 否则只能走相同位路径
                p = node[p].son[d];
                ans |= d << i;
            }
        }
        return ans ^ u; // 返回异或结果（网页15的实现优化）
    }

    // 返回当前树中存储的数字数量
    int size() { return siz; }
};

struct Query {
    int idx, val; // idx: 原始查询索引，val: 查询的xi值
};

class Solution {
public:
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& Q) {
        int m = Q.size();
        std::map<int, std::vector<Query>>
            qry; // 按mi排序查询（网页14的离线处理策略）

        // 重组查询为按mi分组的结构
        for (int i = 0; i < m; i++) {
            qry[Q[i][1]].emplace_back(i, Q[i][0]); // [mi → (原索引, xi)]
        }
        std::vector<int> ans(m, -1);

        Trie tr;
        tr.init(INT_MAX);                    // 初始化处理31位（最大整数值）
        std::sort(nums.begin(), nums.end()); // 排序nums以便逐步插入

        int idx = 0;               // nums的当前插入位置
        for (auto& [k, v] : qry) { // 按mi从小到大处理查询
            // 插入所有≤当前mi的数字（网页14的离线处理关键）
            while (idx < nums.size() && nums[idx] <= k) {
                tr.insert(nums[idx]);
                idx++;
            }

            // 处理该mi下的所有查询
            if (tr.size() > 0) { // 存在有效数字时才计算
                for (auto& i : v) {
                    // 计算xi与最大异或值的异或结果（网页15的核心逻辑）
                    ans[i.idx] = tr.find(i.val);
                }
            }
        }
        return ans;
    }
};